import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-215-数组中的第K个最大元素
 * @date 2025/7/8 14:51
 */
public class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        // 自己实现的快速排序，全部通过
        // 只需要排列k所在的子区域即可
        int n = nums.length;
        // n-k 排序后目标k元素的下标
        return quickSortLargestK(nums, 0, n - 1, n - k);
    }

    private int quickSortLargestK(int[] nums, int left, int right, int targetIndex) {
        if (left >= right) return nums[targetIndex];
        int pivot = nums[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (nums[j] < pivot) {
                i++;
                swap(nums, i, j);
            }
        }

        // 基准理应所在位置为i+1
        int pivotIndex = i + 1;
        swap(nums, pivotIndex, right);

        // 现在只需要排列 targetIndex 所在的子区域即可
        if (targetIndex == pivotIndex) {
            return nums[targetIndex];
        } else if (targetIndex > pivotIndex) {
            return quickSortLargestK(nums, pivotIndex + 1, right, targetIndex);
        } else {
            return quickSortLargestK(nums, left, pivotIndex - 1, targetIndex);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a));
        for (int x : nums) {
            minHeap.offer(x);

            // 动态维护一个容量为k的小根堆
            if (minHeap.size() > k) {
                minHeap.poll();
            }

        }
        return minHeap.poll();
    }
}
